//给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
//输出：6
//解释：[1,1,1,0,0,1,1,1,1,1,1]
//粗体数字从 0 翻转到 1，最长的子数组长度为 6。 
//
// 示例 2： 
//
// 
//输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
//输出：10
//解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
//粗体数字从 0 翻转到 1，最长的子数组长度为 10。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// nums[i] 不是 0 就是 1 
// 0 <= k <= nums.length 
// 
// Related Topics 数组 二分查找 前缀和 滑动窗口 👍 384 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _1004_MaxConsecutiveOnesIii {
    public static void main(String[] args) {
        Solution solution = new _1004_MaxConsecutiveOnesIii().new Solution();
        int[] nums = new int[] {1,1,1,0,0,0,1,1,1,1,0};
        int k = 2;
        System.out.println(solution.longestOnes(nums, k));
    }

    class Solution {
        public int longestOnes(int[] nums, int k) {
            int n = nums.length;
            int left = 0;
            int lsum = 0;
            int rsum = 0;
            int res = 0;
            for (int right = 0; right < n; right++) {
                rsum += 1 - nums[right];
                while (lsum < rsum - k) {
                    lsum += 1 - nums[left];
                    left++;
                }
                res = Math.max(res, right - left + 1);
            }
            return res;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public int longestOnes(int[] nums, int k) {
            int n = nums.length;
            int[] P = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                P[i] = P[i - 1] + (1 - nums[i - 1]);
            }

//            System.out.println(Arrays.toString(P));
            int ans = 0;
            for (int right = 0; right < n; right++) {
                int left = binarySearch(P, P[right + 1] - k);
                ans = Math.max(ans, right - left + 1);
            }

            return ans;
        }
        private int binarySearch(int[] P, int target) {
            int low = 0;
            int high = P.length - 1;
            while (low < high) {
                int mid = (high - low) / 2 + low;
                if (P[mid] < target) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}